Current data processing systems include database management programs. These programs provide easy access to database tables that each consist of a multiple of records. A relational database program provides access to several different database tables where elements of one database table are contained in another database table. The relational database program allows the user to search, access, and alter data contained in several different database tables using a specific element or field that is common to these database tables. For example, one database table may contain employees' names and employees' serial numbers. Another database table may contain employees' names and employees' salaries. A third database table may contain employees' names and employees' locations. A relational database program may allow the user to access employees' names, employees' serial numbers, employees' salaries, and employees' locations and make changes to these tables without having to individually access each database table separately.
An important aspect of the database programs is the capability to provide fast and efficient access to records in the individual database.
More recent data processing systems provide support to a multiple of users simultaneously enabling each user to access data concurrently.
An index file is commonly used by database management programs to provide quick and efficient access to records in tables. These index files are commonly configured in a B-Tree structure. A reference that discusses the B-Tree is "Efficient Locking For Concurrent Operation On B-Tree" by Lehman and Yao, ACM Transactions on Database Systems, volume 6, number 4, Dec., 1981 pages 650-670. Other references addressing B-Tree structures include "The Ubiquitous B-Tree" by Comer, Computing Surveys, volume 11, number 2, June, 1979, pages 121-137; and "Concurrent Operation on B-Trees with Over Taking" by Sagiv, Proceedings ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March, 1985, pages 28-37.
The index file configured as a B-Tree structure consists of a root node with many levels of nodes branching from the root node. The information contained in these nodes include pointers to the nodes at the next level or pointers to records in the database. These pointers include further information termed key record information which may reference the records in the database. The record keys are in an ordered form throughout the nodes. For example, an index tree may exist for an alphabetic listing of employee names. The root node would include reference keyed data that relates to records indirectly or directly referenced by the next level of nodes. The reference keys contain information about the index field, i.e. the alphabetic spelling of the employees name. Therefore, the ordered keys in the root node would point to the next successive level of nodes. In other words, the next successive node may indirectly or directly reference all employees names beginning with A, B, and C. A next successive node, parallel with the first successive node, may contain employee records whose last name begin with the letters D-M. The last successive node on this level would reference records of employees with last names starting with N-Z. As one searches through the index file tree, a bottom node is eventually reached. The contents of the bottom node include record keys that point to the individual records in storage.
One problem in providing concurrent accesses to database tables occurs when multiple transactions are trying to access a record at the same time. Specifically, when one user wishes to change a record and another user is attempting to access this record, a contention situation occurs. One solution to the contention problem is to provide exclusive access (or locking) to the records or to the portions of the B-Tree indexes to insure that the index node, or record is not changed while the user is attempting to access it. Locking is addressed in "Index Locking and Splitting" IBM Technical Disclosure Bulletin, volume 25, number 7B, December, 1982, pages 3725-3729; and "Locking Protocols for Concurrent Operations on B-Trees", IBM Technical Disclosure Bulletin, volume 19, number 10, March, 1977, pages 3887-3889.
The disadvantage to a locking solution is that a lock, while providing access to one user, prevents access by any other user.
It is the object of the present invention to provide a more efficient method of accessing records in a database through an index tree while providing more efficient concurrent access to the database record.
Information in index nodes may be altered during access by several users. These nodes contain the key record information that may be deleted or inserted as records are inserted or deleted into the database table. Information from one node may be moved to another node during a record insert operation because of the limited storage size for a node. The inserting transaction may attempt to move key record information from one node to another in order to accomplish the insertion task. This movement of information during concurrent transaction access may generate error conditions within the concurrent transaction accesses because the index information is being changed. The object of the present invention is to provide concurrent access to the index by several transaction while the index information is being changed without introducing error conditions.